home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-braden-shared-media-00.txt < prev    next >
Text File  |  1993-10-18  |  36KB  |  941 lines

  1.  
  2.  
  3. Internet Draft                                                 R. Braden
  4. Expires: April 1994                                              USC-ISI
  5. <draft-braden-shared-media-00.txt>                            Jon Postel
  6.                                                                  USC-ISI
  7.                                                            Yakov Rekhter
  8.                                                             IBM Research
  9.                                                             October 1993
  10.  
  11.  
  12.  
  13.            Internet Architecture Extensions for Shared Media
  14.  
  15.  
  16. Status of This Memo
  17.  
  18.    This document is an Internet-Draft.  Internet-Drafts are working
  19.    documents of the Internet Engineering Task Force (IETF), its Areas,
  20.    and its Working Groups.  Note that other groups may also distribute
  21.    working documents as Internet-Drafts.
  22.  
  23.    Internet-Drafts are draft documents valid for a maximum of six
  24.    months.  Internet-Drafts may be updated, replaced, or obsoleted by
  25.    other documents at any time.  It is not appropriate to use Internet-
  26.    Drafts as reference material or to cite them other than as a
  27.    ``working draft'' or ``work in progress.''
  28.  
  29. Abstract
  30.  
  31.    The original Internet architecture assumed that each network is
  32.    labeled with a single IP network number.  This assumption is violated
  33.    for shared media, such as large public data networks.  The
  34.    architecture still works if this is violated, but some unnecessary
  35.    host-router and router-router hops may result. This memo discusses
  36.    alternative approaches to extension of the Internet architecture for
  37.    efficient use of shared media.
  38.  
  39.  
  40. 1. INTRODUCTION
  41.  
  42.    This memo concerns the implications of shared medium networks for the
  43.    architecture of the TCP/IP protocol suite.  General familiarity with
  44.    the TCP/IP architecture and the IP protocol is assumed.
  45.  
  46.    The Internet architecture is founded upon what was originally called
  47.    the "Catenet model" [PSC81].  Under this model, the Internet
  48.    (originally dubbed "the Catenet") is formed using routers (originally
  49.    called "gateways") to interconnect distinct and perhaps diverse
  50.    networks.  An IP host address (more correctly characterized as a
  51.  
  52.  
  53.  
  54. Braden, Postel, Rekhter   Expires: April 1994                   [Page 1]
  55.  
  56.  
  57.  
  58.  
  59. Internet Draft        Shared Media IP Architecture          October 1993
  60.  
  61.  
  62.    network interface address) is formed of the pair (net#,host#).  Here
  63.    "net#" is a unique IP number assigned to the network (or subnet) to
  64.    which the host is attached, and "host#" identifies the host on that
  65.    network (or subnet).
  66.  
  67.    The original Internet model made the implicit assumptions that each
  68.    network has a single IP network number and that networks with
  69.    different numbers may interchange packets only through routers.  This
  70.    assumption may be violated for networks implemented using a common
  71.    "shared medium" (SM) at the link layer (LL).  For example, in
  72.    operational environments, network managers sometimes want to
  73.    configure multiple IP network numbers (usually subnet numbers) on a
  74.    single Ethernet.  Potentially more important examples of shared media
  75.    are provided by the proposed large (switched) public data networks
  76.    (LPDNs).
  77.  
  78.    This memo concerns a set of changes that will provide the desired
  79.    efficiency in an SM while retaining the coherence of the existing
  80.    architecture.  This issue has arisen in a number of IETF Working
  81.    Groups concerned with LPDNs, including IPLPDN, IP over ATM, IDRP for
  82.    IP, and BGP.  It is clearly time to take a careful look at the
  83.    architectural issues to be solved.
  84.  
  85.    This memo first summarizes the relevant aspects of the original
  86.    architecture (Section 2), and then it shows the effect of introducing
  87.    shared media networks and the problems to be solved (Section 3).
  88.    Then it discusses possible solutions (Section 4).
  89.  
  90.  
  91. 2. THE ORIGINAL ARCHITECTURE
  92.  
  93.    We very briefly review the original architecture, to introduce the
  94.    terminology and concepts we need.  Figure 1 illustrates a typical set
  95.    of four networks A, ... D, represented traditionally as clouds,
  96.    interconnected by routers R2, R3, and R4.  Routers R1 and R5 connect
  97.    to other parts of the Internet.  Ha,
  98.  
  99.    It is not necessary to distinguish between network and subnet in this
  100.    memo.  We may assume that there is some address mask associated with
  101.    each "network" in Figure 1, allowing a host or router to divide the
  102.    32 bits of an IP address into an address for the cloud and a host
  103.    number that is defined uniquely only within that cloud.
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113. Braden, Postel, Rekhter   Expires: April 1994                   [Page 2]
  114.  
  115.  
  116.  
  117.  
  118. Internet Draft        Shared Media IP Architecture          October 1993
  119.  
  120.  
  121.               Ha           Hb           Hc           Hd
  122.  
  123.               |            |            |            |
  124.               |            |            |            |
  125.              _|_          _|_          _|_          _|_
  126.             (   )        (   )        (   )        (   )
  127.             (Net)        (Net)        (Net)        (Net)
  128.             ( A )        ( B )        ( C )        ( D )
  129.      - R1 --(   )-- R2 --(   )-- R3 --(   )-- R4 --(   )-- R5 --
  130.             (   )        (   )        (   )        (   )
  131.             (___)        (___)        (___)        (___)
  132.  
  133.              Figure 1.  Example Internet Fragment
  134.  
  135.    An Internet router is connected to local network(s) as a special kind
  136.    of host.  Indeed, for network management purposes, a router plays the
  137.    role of a host by originating and terminating datagrams.  However,
  138.    there is an important difference between a host and a router:  the
  139.    routing function is mostly centralized in the routers, allowing hosts
  140.    to be "dumb" about routing.  Internet hosts [RFC-1122] are required
  141.    to make only one simple routing decision: is the destination address
  142.    local to the connected network?  If the address is not local, we say
  143.    it is "foreign" (relative to the connected network).
  144.  
  145.    A host sends a datagram directly to a local destination address, or
  146.    for a foreign destination, to a first-hop router.  The host initially
  147.    uses some "default" router for any new destination address.  If the
  148.    default is the wrong choice, that router returns a Redirect message
  149.    and forwards the datagram.  The Redirect message specifies the
  150.    preferred first-hop router for the given destination address.  The
  151.    host uses this information, which it maintains in a "routing cache"
  152.    [RFC-1122], to determine the first-hop address for subsequent
  153.    datagrams to the same destination.
  154.  
  155.    To actually forward an IP datagram across a network hop, the sender
  156.    must have the link layer (LL) address of the target.  Therefore, each
  157.    host and router must have some "address resolution" procedure to map
  158.    IP address -> LL address.  ARP, used for networks with broadcast
  159.    capability, is the most common address resolution procedure
  160.    [Plummer82].  If there is no LL broadcast capability (or if it is too
  161.    expensive), then there are two other approaches to address
  162.    resolution: local configuration tables, or some server that can be
  163.    consulted using point-to-point transmission in the local medium.  We
  164.    will refer to the last as an "address-resolution server", or AR
  165.    Server.  Hosts would be configured with the LL address(es) of AR
  166.    Server(s), while the servers would ultimately depend upon configured
  167.    tables of LL address(es).
  168.  
  169.  
  170.  
  171.  
  172. Braden, Postel, Rekhter   Expires: April 1994                   [Page 3]
  173.  
  174.  
  175.  
  176.  
  177. Internet Draft        Shared Media IP Architecture          October 1993
  178.  
  179.  
  180.    The examples in this memo use ARP for address resolution.  At least
  181.    some of the LPDN's that are planned will provide sufficient broadcast
  182.    capability to support ARP.  It is important to note that ARP operates
  183.    at the link layer, while the Redirect and routing cache mechanisms
  184.    operate at the IP layer of the protocol stack.
  185.  
  186.  
  187. 3. THE PROBLEMS INTRODUCED BY SHARED MEDIA
  188.  
  189.    Figure 2 shows the same configuration as Figure 1, but now networks
  190.    A, B, C, and D are all within the same shared medium (SM), shown by
  191.    the dashed box enclosing the clouds.  Networks A, ... D are now
  192.    logical IP networks (called LIS's in [Laubach93]) rather than
  193.    physical networks, and each of these logical networks may (or may
  194.    not) be administratively distinct.  The SM allows direct connectivity
  195.    between any two hosts or routers connected to it.  For example, host
  196.    Ha can interchange datagrams directly with host Hd or with router R4.
  197.    A router that has some but not all of its interfaces connected to the
  198.    shared medium is called a "border router"; R5 is an example.
  199.  
  200.  
  201.            Ha           Hb           Hc           Hd
  202.  
  203.            |            |            |            |
  204.       ---- | ---------- | ---------- | ---------- | ----
  205.      |   __|__        __|__        __|__        __|__   |
  206.         (     )      (     )      (     )      (     )
  207.      |  (     )      (     )      (     )      (     )  |
  208.         ( Net )      ( Net )      ( Net )      ( Net )
  209.      |  (  A  )      (  B  )      (  C  )      (  D  )  |
  210.         (     )      (     )      (     )      (     )
  211.      |  (     )      (     )      (     )      (     )  |
  212.         (_____)      (_____)      (_____)      ( ____)
  213.      |    | |          | |          | |          | |    |
  214.       --- | | -------- | | -------- | | -------- | | ---
  215.           | |          | |          | |          | |
  216.     - R1 -   --- R2 ---   --- R3 ---   --- R4 ---   --- R5 ---
  217.  
  218.  
  219.          Figure 2.  Logical IP Networks in Shared Medium
  220.  
  221.  
  222.    Figure 2 illustrates the "classical" model [Laubach93] for use of the
  223.    Internet architecture within a shared medium, i.e., simply applying
  224.    the original Internet architecture described earlier.  This will
  225.    provide correct but not optimal operation.
  226.  
  227.    For example, in the case of two hosts on the same logical network
  228.  
  229.  
  230.  
  231. Braden, Postel, Rekhter   Expires: April 1994                   [Page 4]
  232.  
  233.  
  234.  
  235.  
  236. Internet Draft        Shared Media IP Architecture          October 1993
  237.  
  238.  
  239.    (not shown in Figure 2), the original rules will clearly work; the
  240.    source host will forward a datagram directly in a single hop to a
  241.    host on the same logical network.  The original rules will also work
  242.    for communication between any pair of hosts shown in Figure 2.
  243.    However, the classical model does not take advantage of the direct
  244.    connectivity allowed by the shared medium.
  245.  
  246.    Suppose host Ha wants to send a datagram to Hd; the original
  247.    architecture will use the four-hop path Ha -> R2 -> R3 -> R4 -> Hd
  248.    instead of the direct path Ha -> Hd.  The extra hops may be
  249.    desirable, as they allow the routers to act as administrative
  250.    firewalls.  On the other hand, when such firewall protection is not
  251.    required, it should be possible to take advantage of the shared
  252.    medium to allow this datagram to use shorter paths.  In general, it
  253.    should be possible to choose between firewall security and efficient
  254.    connectivity.  This memo concerns how to achieve minimal-hop
  255.    connectivity when it is desired.
  256.  
  257.    Note that ARP requires LL broadcast.  Even if the SM supports
  258.    broadcast, it is likely that the administrators will erect firewalls
  259.    to keep broadcasts local to their LIS.
  260.  
  261.    There are three cases to be optimized.  Suppose H and H' are hosts
  262.    and Rb and Rb' are border routers connected to the same same SM.
  263.    Then the following one-hop paths should be possible:
  264.  
  265.  
  266.          H -> H':  Host to host within the SM
  267.  
  268.          H -> Rb: Host to exit router
  269.  
  270.          Rb -> Rb': Entry boder router to exit border router,
  271.                      for transit traffic.
  272.  
  273.  
  274.    We may or not be able to remove the extra hop implicit in Rb -> R ->
  275.    H, where the ultimate source is outside the SM.  To remove this hop
  276.    would require distribution of host routes, not just network routes,
  277.    between the two routers R and Rb.
  278.  
  279.    There are a number of important requirements for any architectural
  280.    solution to these problems.
  281.  
  282.    *    Interoperability
  283.  
  284.         Modified hosts and routers must interoperate with unmodified
  285.         nodes.
  286.  
  287.  
  288.  
  289.  
  290. Braden, Postel, Rekhter   Expires: April 1994                   [Page 5]
  291.  
  292.  
  293.  
  294.  
  295. Internet Draft        Shared Media IP Architecture          October 1993
  296.  
  297.  
  298.    *    Practicality
  299.  
  300.         Minimal software changes should be required.
  301.  
  302.    *    Robustness
  303.  
  304.         The new scheme must be robust against errors in software,
  305.         configuration, or transmission.
  306.  
  307.    *    Security
  308.  
  309.         The new scheme must be securable against subversion.
  310.  
  311.    The distinction between host and router is very significant from an
  312.    engineering viewpoint.  It is considered to be much harder to make a
  313.    global change in host software than to change router software,
  314.    because there are many more hosts and host vendors than routers and
  315.    router vendors, and because hosts are less centrally administered
  316.    than routers.  If it is necessary to change the specification of what
  317.    a host does (and it is), then we must minimize the extent of this
  318.    change.
  319.  
  320.  
  321. 4. SOME SOLUTIONS TO THE SM PROBLEMS
  322.  
  323.    Four different approaches have been suggested for solving these SM
  324.    problems.
  325.  
  326.    (1)  Iterated Redirects
  327.  
  328.         In this approach, the host Redirect mechanism is extended to
  329.         collapse multiple-hop paths within the same shared medium, hop-
  330.         by-hop.  A router will be allowed to send, and a host will be
  331.         allowed to accept, a Redirect message that specifies a foreign
  332.         IP address within the same SM.  We refer to this as a "foreign
  333.         Redirect".
  334.  
  335.    (2)  Extended Routing
  336.  
  337.         Routing protocols can be modified to know about the SM and to
  338.         provide LL addresses.
  339.  
  340.    (3)  Extended Proxy ARP
  341.  
  342.         This is a form of the proxy ARP approach, in which the routing
  343.         problem is solved implicitly by an extended address resolution
  344.         mechanism at the LL.  This approach has been described by
  345.         Heinanen [Heinanen93] and by Garrett et al [Garratt93].
  346.  
  347.  
  348.  
  349. Braden, Postel, Rekhter   Expires: April 1994                   [Page 6]
  350.  
  351.  
  352.  
  353.  
  354. Internet Draft        Shared Media IP Architecture          October 1993
  355.  
  356.  
  357.    (4)  Route Query Messages
  358.  
  359.         This approach has been suggested by Halpern [Halpern93].  Rather
  360.         than adding additional information to routing, this approach
  361.         would add a new IP-layer mechanism, end-to-end query and reply
  362.         datagrams.
  363.  
  364.    These four are discussed in the following four subsections.
  365.  
  366.       4.1  Hop-by-Hop Redirection
  367.  
  368.       The first scheme we consider would operate at the IP layer.  It
  369.       would cut out extra hops one by one, with each router in the path
  370.       operating on local information only.  This approach requires both
  371.       host and router changes but no routing protocol changes.
  372.  
  373.       The basic idea is that the first-hop router, upon observing that
  374.       the next hop is within the same SM, sends a foreign Redirect to
  375.       the source, redirecting it to the next hop.  Successive
  376.       application of this algorithm at each intermediate router will
  377.       eventually result in a direct path from source host to destination
  378.       host, if both are within the same SM.
  379.  
  380.       Suppose that Ha wants to send a datagram to Hd.  We use the
  381.       notation IP.a for the IP address of entity a, and LL.a for the
  382.       corresponding LL address.  Each line in the following shows an IP
  383.       datagram and the path that datagram will follow, separated by a
  384.       colon.  The notation "Redirect( h, IP.a)" means a Redirect
  385.       specifying IP.a as the best next hop to reach host h.
  386.  
  387.          (1)  Datagram 1: Ha -> R2 -> R3 -> R4 -> Hd
  388.  
  389.          (2)  Redirect(Hd, IP.R3): R2 -> Ha
  390.  
  391.          (3)  Datagram 2: Ha -> R3 -> R4 -> Hd
  392.  
  393.          (4)  Redirect(Hd, IP.R4): R3 -> Ha
  394.  
  395.          (5)  Datagram 3: Ha -> R4 -> Hd
  396.  
  397.          (6)  Redirect(Hd, IP.Hd): R4 -> Ha
  398.  
  399.          (7)  Datagram 4: Ha -> Hd
  400.  
  401.       There are three problems to be solved to make this work.
  402.  
  403.       IR1: Each router must be able to resolve the LL address of the
  404.            source Ha, to send a (foreign) Redirect.
  405.  
  406.  
  407.  
  408. Braden, Postel, Rekhter   Expires: April 1994                   [Page 7]
  409.  
  410.  
  411.  
  412.  
  413. Internet Draft        Shared Media IP Architecture          October 1993
  414.  
  415.  
  416.            Let us assume that the link layer provides the source LL
  417.            address when an IP datagram arrives.  If the router
  418.            determines that a Redirect should be sent, then it will be
  419.            sent to the source LL address of the received datagram.
  420.  
  421.       IR2: A source host must be able to resolve the LL address of each
  422.            router to which it is redirected.
  423.  
  424.            It would be possible for each router R, upon sending a
  425.            Redirect to Ha, to also send an unsolicited ARP Reply point-
  426.            to-point to LL.Ha, updating Ha's ARP cache with LL.R.
  427.            However, there is not guarantee that this unsolicited ARP
  428.            Reply would be delivered.  If it was lost, there would be a
  429.            forwarding black hole.  The host could recover by starting
  430.            over from the original default router; however, this may be
  431.            too obtuse a solution.
  432.  
  433.            A much more direct solution would introduce an extended ICMP
  434.            Redirect message (call it XRedirect) that carries the LL
  435.            address as well as the IP address of the target.  This
  436.            removes the issue of reliable delivery of the unsolicited ARP
  437.            described earlier, because the fate of the LL address is
  438.            shared with the IP target address; both are delivered or
  439.            neither are.
  440.  
  441.            Using XRedirect and omitting the spurious router-router
  442.            XRedirects, the previous example becomes:
  443.  
  444.               (1)  Datagram 1: Ha -> R2 -> R3 -> R4 -> Hd
  445.  
  446.               (2)  XRedirect(Hd, IP.R3, LL.R3): R2 -> Ha
  447.  
  448.               (3)  Datagram 2: Ha -> R3 -> R4 -> Hd
  449.  
  450.               (4)  XRedirect(Hd, IP.R4, LL.R4): R3 -> Ha
  451.  
  452.               (5)  Datagram 3: Ha -> R4 -> Hd
  453.  
  454.               (6)  XRedirect(Hd, IP.Hd, LL.Hd): R4 -> Ha
  455.  
  456.               (7)  Datagram 4: Ha -> Hd
  457.  
  458.       IR3: Each router should be able to recognize when it is the first
  459.            hop in the path, since a Redirect should be sent only by the
  460.            first hop router.  Unfortunately this is not generally
  461.            possible, since a router in this chain determines the LL
  462.            address of the source only from the arriving datagram, as
  463.            indicated in IR1 above.  Therefore, application of this
  464.  
  465.  
  466.  
  467. Braden, Postel, Rekhter   Expires: April 1994                   [Page 8]
  468.  
  469.  
  470.  
  471.  
  472. Internet Draft        Shared Media IP Architecture          October 1993
  473.  
  474.  
  475.            technique by routers in the path after the first-hop router
  476.            will cause them to send spurious [X]Redirects; these will be
  477.            sent to the IP address of the source host, but using the LL
  478.            address of the previous-hop router.  These will be ignored by
  479.            the routers and cause no harm.
  480.  
  481.  
  482.       The Host Requirements RFC [RFC-1122] specifies the host mechanism
  483.       for routing an outbound datagram in terms of sending the datagram
  484.       either directly to a local destination or else to the first hop
  485.       router to reach a foreign destination [RFC-1122 3.3.1].  However,
  486.       if the routing cache did specify a foreign target address, the
  487.       mechanism as described should forward the datagram directly to
  488.       that foreign address, as we require for efficient SM operation.
  489.  
  490.       The target address contained in the routing cache is updated by
  491.       Redirect messages.  There is currently a restriction on what
  492.       target addresses may be accepted in Redirect messages [RFC-1122
  493.       3.2.2.2]:
  494.  
  495.            A Redirect message SHOULD be silently discarded if the new
  496.            router address it specifies is not on the same connected
  497.            (sub-) net through which the Redirect arrived, or if the
  498.            source of the Redirect is not the current first-hop router
  499.            for the specified destination.
  500.  
  501.       The minimal change for SMs would remove the first validity check
  502.       and generalize the second, as follows:
  503.  
  504.            A Redirect message SHOULD be silently discarded if the source
  505.            of the Redirect is not the current target address in the
  506.            routing cache for the specified destination.
  507.  
  508.       Thus, the new validation test is that a Redirect must come from
  509.       the node to which we sent the datagram that triggered the
  510.       Redirect.
  511.  
  512.       In order to send a datagram to the target address found in the
  513.       routing cache, a host must resolve the IP address into a LL
  514.       address.  We assume that no change is necessary in the current
  515.       IP->LL resolution mechanism in the host to handle a foreign rather
  516.       than a local address.  Thus, the only change required of a host is
  517.       to remove one of the validity checks on a Redirect message.
  518.  
  519.       By design, the router changes required to improve SM efficiency
  520.       are much more extensive than the host changes.  The examples given
  521.       earlier showed two kinds of additional router function.
  522.  
  523.  
  524.  
  525.  
  526. Braden, Postel, Rekhter   Expires: April 1994                   [Page 9]
  527.  
  528.  
  529.  
  530.  
  531. Internet Draft        Shared Media IP Architecture          October 1993
  532.  
  533.  
  534.       (1)  Sending Foreign Redirects
  535.  
  536.            Consider a router that is connected to an SM.  When it
  537.            receives a datagram, it tests whether the next hop is on the
  538.            same SM, and if so, it sends a foreign XRedirect to the
  539.            source host, using the link layer address with which the
  540.            datagram arrived.
  541.  
  542.            A router should avoid sending more than a limited number of
  543.            successive foreign Redirects to the same host.  This is
  544.            necessary because an unmodified host may legitimately ignore
  545.            a Redirect to a foreign network and continue to forward
  546.            datagrams to the same router.  A router can accomplish this
  547.            limitation by keeping a cache of foreign Redirects sent.
  548.  
  549.            Note that foreign Redirects generated by routers according to
  550.            these rules, like the current local Redirects, may travel
  551.            exactly one link-layer hop.  It is therefore reasonable and
  552.            desirable to set their TTL to 1, to ensure they cannot stray
  553.            outside the SM.
  554.  
  555.       (2)  SM-wise Routing
  556.  
  557.            A modified routing protocol could allow a router to know
  558.            which other routers are in the same SM, in order to forward a
  559.            datagram directly to the last hop router within the SM.  This
  560.            is discussed in the following section.
  561.  
  562.  
  563.    4.2  Extended Routing
  564.  
  565.       The routing protocols may be modified to carry additional
  566.       information that is specific to the SM.  The router could use the
  567.       attribute "SameSM" for a route to deduce the shortest path to be
  568.       reported to its neighbors.  It could also carry the LL addresses
  569.       with each router IP address.
  570.  
  571.       For example, the modified routing protocol would allow R2 to know
  572.       that R4 is the best next-hop to reach the destination network in
  573.       the same SM, and to know both IP.R4 and LL.R4.  Then if Ha sends a
  574.       datagram to Hd:
  575.  
  576.           (1) Datagram 1: Ha -> R2 -> R4 -> Hd
  577.  
  578.           (2) XRedirect(Hd, IP.R4, LL.R4): R2 -> Ha
  579.  
  580.           (3) Datagram 2: Ha -> R4 -> Hd
  581.  
  582.  
  583.  
  584.  
  585. Braden, Postel, Rekhter   Expires: April 1994                  [Page 10]
  586.  
  587.  
  588.  
  589.  
  590. Internet Draft        Shared Media IP Architecture          October 1993
  591.  
  592.  
  593.           (4) XRedirect(Hd, IP.Hd, LL.Hd): R4 -> Ha
  594.  
  595.           (5) Datagram 3: Ha -> Hd
  596.  
  597.       Note that we require the routing protocol to handle only per-
  598.       network information, not per-host information.  This results in
  599.       the two-step redirection shown in this example.
  600.  
  601.       There are three aspects to the routing protocol modification.
  602.  
  603.       (1)  The ability to pass "third-party" information -- a router
  604.            should be able to specify the address (IP address and perhaps
  605.            LL address) of some other router as the next-hop.
  606.  
  607.       (2)  Knowledge of the "SameSM" attribute for routes.
  608.  
  609.       (3)  The LL addresses corresponding to IP addresses of routers
  610.            within the same SM.
  611.  
  612.       A router must be able to determine that a particular IP address
  613.       (e.g., the source address) is in the same SM.  There are several
  614.       possible ways to make this information available to a router in
  615.       the SM.
  616.  
  617.       (1)  A router may use a single physical interface to an SM; this
  618.            implies that all its logical interfaces lie within the same
  619.            SM.
  620.  
  621.       (3)  There might be some administrative structure in the IP
  622.            addresses, e.g., all IP addresses within a particular
  623.            national SM might have a common prefix string.
  624.  
  625.       (3)  There might be configuration information, either local to the
  626.            router or available from some centralized server (e.g, the
  627.            DNS).  Note that a router could consult this server in the
  628.            background while continuing to forward datagrams without
  629.            delay.  The only consequence of a delay in obtaining the
  630.            "Same SM" information would be some unnecessary (but
  631.            temporary) hops.
  632.  
  633.  
  634.    4.3 Extended Proxy ARP
  635.  
  636.       The approach of Heinanen [Heinanen93] was intended to solve the
  637.       problem of address resolution in a shared medium with no broadcast
  638.       mechanism ("Non-Broadcast, MultiAccess" or NBMA).  Imagine that
  639.       the shared medium has a single IP network number, i.e., it is one
  640.       network "cloud".  He envisions a set of AR Servers within this
  641.  
  642.  
  643.  
  644. Braden, Postel, Rekhter   Expires: April 1994                  [Page 11]
  645.  
  646.  
  647.  
  648.  
  649. Internet Draft        Shared Media IP Architecture          October 1993
  650.  
  651.  
  652.       medium.  These AR Servers run some routing protocol among
  653.       themselves.  A source host issues an ARP Request (via a point-to-
  654.       point LL transmission) to an AR Server with which it is
  655.       associated.  This ARP Request is forwarded hop-by-hop at the link
  656.       layer, through the AR Servers towards the AR Server that is
  657.       associated with the destination host.  That AR Server resolves the
  658.       address (using information learned from either host advertisement
  659.       or a configuration file), and returns an ARP Reply back through
  660.       the AR Servers to the source host.
  661.  
  662.               Ha           Hb           Hc           Hd
  663.  
  664.               |            |            |            |
  665.          ---- | ---------- | ---------- | ---------- | ----
  666.         (                                                  )
  667.         (        Shared Medium (One Logical Network)       )
  668.         (                                                  )
  669.          ----|--|---------|------------|----------|----|---
  670.              |  |         |            |          |    |
  671.        - R1 -   |         |            |          |    --- R5 ---
  672.             ____|__     __|____      __|____     _|_____
  673.            | AR Sa |   | AR Sb |    | AR Sc |   | AR Sd |
  674.            |_______|   |_______|    |_______|   |_______|
  675.  
  676.  
  677.             Figure 3.  Single-Cloud Shared Medium
  678.  
  679.  
  680.       Figure 3 suggests that each of the hosts Ha, ... Hd is associated
  681.       with a corresponding AR Server "AR Sa", ..."AR Sd".
  682.  
  683.       This same scheme could be applied to the LIS model of Figure 2.
  684.       The AR Servers would be implemented in the routers, and if the
  685.       medium supports broadcast then the hosts would be configured for
  686.       proxy ARP.  That is, the host would be told that all destinations
  687.       are local, so it will always issue an ARP request for the final
  688.       destination.  The set of AR Servers would resolve this request.
  689.  
  690.       Since routing loops are a constant possibility, Heinanen's
  691.       proposal includes the addition of a hop count to ARP requests and
  692.       replies.
  693.  
  694.       Like all proxy ARP schemes, this one has a seductive simplicity.
  695.       However, solving the SM problem at the LL has several costs.  It
  696.       requires a complete round-trip time before the first datagram can
  697.       flow.  It requires a hop count in the ARP packet.  This seems like
  698.       a tip-off that the link layer is not the most appropriate place to
  699.       solve the SM problem in general.
  700.  
  701.  
  702.  
  703. Braden, Postel, Rekhter   Expires: April 1994                  [Page 12]
  704.  
  705.  
  706.  
  707.  
  708. Internet Draft        Shared Media IP Architecture          October 1993
  709.  
  710.  
  711.    4.4  Routing Query Messages
  712.  
  713.       This scheme [Halpern93] introduces a new IP level mechanism: SM
  714.       routing query and reply messages.  These messages are forwarded as
  715.       IP datagrams hop-by-hop in the direction of the destination
  716.       address.  The exit router can return a reply, again hop-by-hop,
  717.       that finally reaches the source host as an XRedirect.  It would
  718.       also be possible (but not necessary) to modify hosts to initiate
  719.       these queries.
  720.  
  721.       The query/reply pair is supplying the same information that we
  722.       would add to routing protocols under Extended Routing.  However,
  723.       the Query/Reply messages would allow us to keep the current
  724.       routing protocols unchanged, and would also provide the extra
  725.       information only for the routes that are actually needed, thus
  726.       reducing the routing overhead.  Note that the Query/Reply sequence
  727.       can happen in parallel with forwarding the initial datagram hop-
  728.       by-hop, so it does not add an extra round-trip delay.
  729.  
  730. 5.  Security Considerations
  731.  
  732.    We should discuss the security issues raised by our suggested
  733.    changes.  We should note that we are not talking about "real"
  734.    security here; real Internet security will require cryptographic
  735.    techniques on an end-to-end basis.  However, it should not be easy to
  736.    subvert the basic delivery mechanism of IP to cause datagrams to flow
  737.    to unexpected places.
  738.  
  739.    With this understanding, the security problems arise in two places:
  740.    the ICMP Redirect messages and the ARP replies.
  741.  
  742.    *    ICMP Redirect Security
  743.  
  744.         We may reasonably require that the routers be secure.  They are
  745.         generally under centralized administrative control, and we may
  746.         assume that the routing protocols will contain sufficient
  747.         authentication mechanisms (even if it is not currently true).
  748.         Therefore, a host will reasonably be able to trust a Redirect
  749.         that comes from a router.
  750.  
  751.         However, it will NOT be reasonable for a host to trust another
  752.         host.  Suppose that the target host in the examples of Section
  753.         4.1 is untrustworthy; there is no way to prevent its issuing a
  754.         new Redirect to some other destination, anywhere in the
  755.         Internet.  On the other hand, this exposure is no worse than it
  756.         was; the target host, once subverted, could always act as a
  757.         hidden router to forward traffic elsewhere.
  758.  
  759.  
  760.  
  761.  
  762. Braden, Postel, Rekhter   Expires: April 1994                  [Page 13]
  763.  
  764.  
  765.  
  766.  
  767. Internet Draft        Shared Media IP Architecture          October 1993
  768.  
  769.  
  770.    *    ARP Security
  771.  
  772.         Currently, an ARP Reply can come only from the local network,
  773.         and a physically isolated network  can be administrative secured
  774.         from subversion of ARP.  However, an ARP Reply can come from
  775.         anywhere within the SM, and an evil-doer can use this fact to
  776.         divert the traffic flow from any host within the SM
  777.         [Bellovin89].
  778.  
  779.         The XRedirect closes this security hole.  Validating the
  780.         XRedirect (as coming from the node to which the last datagram
  781.         was sent) will also validate the LL address.
  782.  
  783.         Another approach is to validate the source address from which
  784.         the ARP Reply was received (assuming the link layer protocol
  785.         carries the source address and the driver supplies it).  An
  786.         acceptable ARP reply for destination IP address D can only come
  787.         from LL address x, where the routing cache maps D -> E and the
  788.         ARP cache gives x as the translation of E.  This validation,
  789.         involving both routing and ARP caches, might be ugly to
  790.         implement in a strictly-layered implementation.  It would be
  791.         natural if layering were already violated by combining the ARP
  792.         cache and routing cache.
  793.  
  794.    It is possible for the link layer to have security mechanisms that
  795.    could interfere with IP-layer connectivity.  In particular, there
  796.    could possible be non-transitivity of logical interconnection within
  797.    a shared medium.  In particular, some large public data networks may
  798.    include configuration options that could allow Net A to talk to Net B
  799.    and Net B to talk to Net C, but prevent A from talking directly to C.
  800.    In this case, the routing protocols have to be sophisticated enough
  801.    to handle such anomalies.
  802.  
  803. 6.  CONCLUSIONS
  804.  
  805.    We have outlined four possible extensions to the Internet
  806.    architecture to allow hop-efficient forwarding of IP datagrams within
  807.    shared media.  The changes to hosts are minimal (indeed, some hosts
  808.    may require no changes at all).  The changes to routers are more
  809.    extensive, but can be introduced gradually.
  810.  
  811.    Our suggested extensions do not change the overall structure of the
  812.    Internet architecture.  It would be possible to make (and some have
  813.    suggested) much more radical changes to accommodate shared media.  In
  814.    the extreme, one could entirely abolish the inner clouds in Figure 2,
  815.    so that there would be no logical network structure within the SM.
  816.    The IP addresses would then be logical, and some mechanism of
  817.    distributed servers would be needed to find routes within this random
  818.  
  819.  
  820.  
  821. Braden, Postel, Rekhter   Expires: April 1994                  [Page 14]
  822.  
  823.  
  824.  
  825.  
  826. Internet Draft        Shared Media IP Architecture          October 1993
  827.  
  828.  
  829.    haze.  We think that throwing out what has been proven to work, and
  830.    work well, might make a good research paper but would not be good
  831.    Internet design strategy.
  832.  
  833. 7. ACKNOWLEDGMENTS
  834.  
  835.    We are grateful to Keith McGloghrie, Joel Halpern, and others who
  836.    rubbed our noses in this problem.  We are also grateful to Gerri
  837.    Gilliland who supplied the paper tablecloth, colored crayons, and
  838.    fine food that allowed these ideas to be assembled initially.
  839.  
  840. 8.  REFERENCES
  841.  
  842.  
  843.       [Bellovin89] Bellovin, S. M., "Security Problems in the TCP/IP
  844.       Protocol Suite".  ACM CCR, v. 19. no. 2, April 1989.
  845.  
  846.       [Garrett93]  Garrett, J., Hagan, J. and J. Wong, "Directed ARP",
  847.       RFC-1433, March 1993.
  848.  
  849.       [Plummer82]  Plummer, D., "An Ethernet Address Resolution
  850.       Protocol", RFC-826, November 1982.
  851.  
  852.       [Halpern93]  Halpern, J., Private communication, July 1993.
  853.  
  854.       [Heinanen93]  Heinanen, J., "NBMA Address Resolution Protocol
  855.       (NBMA ARP)", Work in Progress, June 1993.
  856.  
  857.       [Laubach93]  Laubach, M., "Classical IP and ARP over ATM", work in
  858.       progress, July 1993.
  859.  
  860.       [Postel81a]  Postel, J., "Internet Protocol", RFC-791, September
  861.       1981.
  862.  
  863.       [Postel81b]  Postel, J., "Internet Control Message Protocol",
  864.       RFC-792, September 1981.
  865.  
  866.       [PSC81]  Postel, J., Sunshine, C., and D. Cohen, "The ARPA
  867.       Internet Protocol".  Computer Networks 5, pp 261-271, 1983.
  868.  
  869.       [RFC-1122]  Braden, R., Ed., "Requirements for Internet Hosts --
  870.       Communication Layers", RFC-1122, October 1989.
  871.  
  872.  
  873. Security Considerations
  874.  
  875.    See Section 5 of this memo.
  876.  
  877.  
  878.  
  879.  
  880. Braden, Postel, Rekhter   Expires: April 1994                  [Page 15]
  881.  
  882.  
  883.  
  884.  
  885. Internet Draft        Shared Media IP Architecture          October 1993
  886.  
  887.  
  888. Authors' Addresses
  889.  
  890.  
  891.    Bob Braden
  892.    University of Southern California
  893.    Information Sciences Institute
  894.    4676 Admiralty Way
  895.    Marina del Rey, CA 90292
  896.  
  897.    Phone: (213) 822-1511
  898.    EMail: Braden@ISI.EDU
  899.  
  900.    Jon Postel
  901.    University of Southern California
  902.    Information Sciences Institute
  903.    4676 Admiralty Way
  904.    Marina del Rey, CA 90292
  905.  
  906.    Phone: (213) 822-1511
  907.    EMail: Postel@ISI.EDU
  908.  
  909.    Yakov Rekhter
  910.    Office 32-017
  911.    T.J. Watson Research Center, IBM Corp.
  912.    P.O. Box 218,
  913.    Yorktown Heights, NY 10598
  914.  
  915.    Phone: (914) 945-3896
  916.    EMail: Yakov@WATSON.IBM.COM
  917.  
  918.  
  919.  
  920.  
  921.  
  922.  
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939. Braden, Postel, Rekhter   Expires: April 1994                  [Page 16]
  940.  
  941.